Conventional cellular communication systems adopt a method for routing communication information between nodes of the system. Communication networks, such as those used to deliver telecommunications, to interconnect computers, and the like, may include any number of nodes. The networks may deliver electronic communications between two points by routing the communications from node to node within the network. As the number of nodes in a network increases and as the number of communication paths available to each network node increases, the number of potential paths available for delivering any single communication likewise increases. Accordingly, the problem of selecting an appropriate path through the network arises. Typically, a network attempts to select the shortest possible path to minimize delay, to consume a minimal amount of network resources, and to maximize reliability in delivering a communication. At the same time, a network needs to balance this concern with a need to prevent communication traffic bottlenecks and a need to achieve the highest possible probability that a communication will be delivered to its intended destination.
In a global communication system where nodes are space based and moving with respect to each other, routing mechanisms which involve simple processing and decision making within the nodes are desirable. Furthermore, minimal exchange of any route information in the network in order to minimize node complexity and simplify route management for increased reliability and reduced cost are also desirable. Where the nodes of the communication system include satellites and there may be a possibility of satellite node and link failures, adaptive routing is desirable to balance out the traffic load over moving satellite nodes and changing cross-link capacities. Adaptive routing is also desirable to balance changing traffic load and call flow pattern over time.
Prior art techniques for adaptive routing, when implemented in a distributed fashion, require the exchange of routing update information among the network nodes. They also require processing within the node. These techniques can create synchronization problems in a satellite based network due to longer inter-satellite propagation delays. In addition, such techniques consume the scarce radio bandwidth resources. Prior art techniques also require maintenance and management of routing tables within the nodes which can take up space and also increase the possibility of error.
Alternative means of implementing adaptive routing includes centralized versions where updated routes are calculated in a centralized location and the information is either transmitted to each node in the form of a table, or otherwise distributed to each call processing gateway and used to select the optimum route at the time of establishing a call. This sort of adaptive routing is called source routing and has been implemented by some existing packet networks such as Tymnet. However, in ground based communication networks such as in Tymnet, all calls are normally processed by a single central supervisor which calculates and maintains the updated route information for each possible source-destination pair in the network. Since that single resource selects routes for each call and assigns so-called "virtual circuit" identifiers to each call, the uniqueness of such route identification is maintained for all calls throughout the network, and no confusion is created when several calls cross through one intermediate node on their journey through the network.
This situation is quite different in a global satellite based communication network where up to 20 gateways share the call processing load. Each call may be routed to and processed by a different gateway. Each gateway needs to keep track of the virtual circuit identifiers assigned to calls by other gateways in real time so that the same virtual circuit is not re-used by another gateway in identifying a route for a new call processed by that gateway. The complexity and inefficiency associated with real time exchange of route identification information among several remotely located gateways in a global communication network is undesirable.
Thus what is needed is a method and apparatus of routing data packets among nodes in a communication system where the nodes are moving with respect to each other, and where the connections or links between the nodes are changing as a function of the position of the node. What is also needed is a highly distributed routing method that is implemented autonomously by each node. What is also needed is a routing method which achieves uniforminity in the usage of network links while limiting number of hops on each path used for routing. What is also needed is a routing method which achieves uniforminity in the usage of network links while preventing link congestion. What is also needed is a routing method that actually prevents congestion, rather than reacting to it. What is also needed is a routing method that is link failure proof and routes data packets around link failures.